package DP;

import org.junit.Test;

import java.util.Arrays;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: DP
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-22  15:09
 * @Description: TODO
 * @Version: 1.0
 */
public class 不同路径II63 {

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        if (m <= 0) {
            return 0;
        }
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
            return 0;
        }
        // 初始化
        dp[0][0] = 1;
        // 初始化
        for (int i = 1; i < m; i++) {
            if (obstacleGrid[i][0] != 1) {
                dp[i][0] = dp[i - 1][0];
            }
        }
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[0][j] != 1) {
                dp[0][j] = dp[0][j - 1];
            }
        }
        // 遍历
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i - 1][j] == 1 && obstacleGrid[i][j - 1] != 1) {
                    dp[i][j] = dp[i][j - 1];
                } else if (obstacleGrid[i - 1][j] != 1 && obstacleGrid[i][j - 1] == 1) {
                    dp[i][j] = dp[i - 1][j];
                } else if (obstacleGrid[i - 1][j] != 1 && obstacleGrid[i][j - 1] != 1) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }

    @Test
    public void test() {
        int i = uniquePathsWithObstacles(new int[][]{{0, 1, 0, 0, 0}, {1, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}});
        System.out.println(i);
    }
}
